/**
  * 用了递归
  */
object InsertionSort {
  def isort(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert(xs.head, isort(xs.tail))

  def insert(x: Int, xs: List[Int]): List[Int] =
  //判断是否为空，  比较数值大小 ，  合并集合
    if (xs.isEmpty || x <= xs.head) x :: xs
    //递归
    else xs.head :: insert(x, xs.tail)

  def main(args: Array[String]) {
    println("isort(List(5, 3, 12)) [" + isort(List(5, 3, 12)) + "]")

  }
}
